#include <cstdio>
#include <cstring>

typedef long long ll;
const int N = 100005, mod = 1e9 + 9;
int n, t, a[N], b[N], to[N], cnt;
ll ans, fact[N] = {1};
bool vis[N];

int dfs(int x, int len) {
  if (vis[x]) return len;
  vis[x] = true;
  dfs(to[x], len + 1);
}

inline ll qpow(ll base, int exp) {
  ll res = 1;
  while (exp) {
    if (exp & 1) res = res * base % mod;
    base = base * base % mod;
    exp >>= 1;
  }
  return res;
}

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("testdata.in", "r", stdin);
  freopen("testdata.out", "w", stdout);
#else
  freopen("CppTest.in", "r", stdin);
  freopen("CppTest.out", "w", stdout);
#endif
#endif

  scanf("%d", &t);
  for (int i = 1; i < N; ++i) {
    fact[i] = fact[i - 1] * i % mod;
  }
  while (t--) {
    cnt = 0;
    memset(vis, 0, sizeof(vis));
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
      scanf("%d", &a[i]);
      to[i] = a[i];
    }
    for (int i = 1; i <= n; ++i) {
      if (!vis[i]) {
        b[++cnt] = dfs(i, 0);
      }
    }
    ans = fact[n - cnt];
    for (int i = 1; i <= cnt; ++i) {
      if (b[i] != 1)
        ans = ans * qpow(b[i], b[i] - 2) % mod * qpow(fact[b[i] - 1], mod - 2) % mod;
    }
    printf("%lld\n", ans);
  }
  return 0;
}